//
//  main.c
//  C_Study
//
//  Created by rui on 12-8-28.
//  Copyright (c) 2012年 Wang Rui. All rights reserved.
//



/*
 @要点：树，顺序存储(静态),动态的再构造一个结构体，算法基本一致。
 */

#include "types.h"

#define CHAR 0

#if CHAR
	typedef char TElemType;
	#define Nil ' '
	#define form "%c"
#else
	typedef int TElemType;
	#define Nil 0
	#define form "%d"
#endif


#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */
typedef TElemType SqBiTree[MAX_TREE_SIZE]; /*SqBiTree为含 MAX_TREE_SIZE 个TElemType的数组,0号单元存储根结点*/

typedef struct
{
	int level,order; /* 结点的层,本层序号(按满二叉树计算) */
}position;


/**********************************/
/*@顺序存储二叉树基本操作            */
/**********************************/

#define clearBiTree initBiTree  /* 在顺序存储结构中，两函数完全一样 */
#define destroyTree initBiTree  /* 在顺序存储结构中，两函数完全一样 */

void initTree(SqBiTree T){
	for (int i = 0; i<MAX_TREE_SIZE; i++) {
		T[i] = Nil;
	}
}

void creatBiTree(SqBiTree T){
	initTree(T);
#if CHAR
	printf("请按层序输入结点的值(字符),结点数≤%d:\n",MAX_TREE_SIZE);
    char a[MAX_TREE_SIZE];
	scanf("%s",a);
	for (int i=0; i<strlen(a); i++) {
		T[i] = a[i];
	}
#else
	int i = 0;
	printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤%d:\n",MAX_TREE_SIZE);
	while(TRUE)
	{
		scanf("%d",&T[i]);
		if(T[i]==999)
		{
			T[i]=Nil;
			break;
		}
		i++;
	}
#endif
	for(int j=1;j<MAX_TREE_SIZE;j++)
		if(T[(j+1)/2-1] == Nil && T[j]!= Nil) /* 此非根结点(不空)无双亲 */
		{
			printf("出现无双亲的非根结点"form",位置:%d\n",T[j],j);
			exit(ERROR);
		}
	
}

bool is_empty(SqBiTree T){
	return T[0] == Nil;
}

int biTree_depth(SqBiTree T)
{/* 初始条件：二叉树T存在。操作结果：返回T的深度 */
	int i,j=-1;
	for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最后一个结点 */
		if(T[i]!=Nil)
			break;
	i++; //此时i代表完全二叉树的节点数
	
	do
		j++;
	while(i<pow(2,j));//2的j次方
	
	return j;
}

Status rootNode(SqBiTree T,TElemType *rootNode)
{/* 初始条件：二叉树T存在。操作结果：当T不空，用e返回T的根，返回OK；否则返回ERROR，e无定义 */
	
	if (is_empty(T)) {
		return ERROR;
	}
	else {
		*rootNode = T[0];
	} 
	
	return OK;
}

TElemType Value(SqBiTree T,position e)
{ 	/* 初始条件：二叉树T存在，e是T中某个结点(的位置) */
	/* 操作结果：返回处于位置e(层,本层序号)的结点的值 */
	
	return T[(int)pow(2,e.level-1)+e.order-2];
}

Status Assign(SqBiTree T,position e,TElemType value)
{ /* 初始条件：二叉树T存在，e是T中某个结点(的位置) */
	/* 操作结果：给处于位置e(层,本层序号)的结点赋新值value */
	int i=(int)pow(2,e.level-1)+e.order-2; /* 将层、本层序号转为矩阵的序号 */
	if(value!=Nil&&T[(i+1)/2-1]==Nil) /* 给叶子赋非空值但双亲为空 */
		return ERROR;
	else if(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /*  给双亲赋空值但有叶子(不空) */
		return ERROR;
	T[i]=value;
	return OK;
}


/**********************************/
/*@辅助函数						  */
/**********************************/

void visit(TElemType e)
{
	printf("%c",e);
}


/**********************************/
/* @main函数                       */
/**********************************/
int main(int argc, const char * argv[])
{
	SqBiTree T;
	creatBiTree(T);
	
	printf("depth:%d",biTree_depth(T));
	
	return 0;
}

